﻿// Study0310.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
// 第三章：函数 递归
//汉诺塔问题
//有三根针A、B、C。A针上有N个盘子，大的在下，小的在上，要求把这N个盘子从A针移到C针，在移动过程中可以借助B针，
//每次只允许移动一个盘，且在移动过程中在三根针上都保持大盘在下，小盘在上。
//分析： 将n 个盘子从A针移到C针可以分解为三个步骤：
//1  将A 上n - 1个盘子移到 B针上（借助C针）；
//2  把A针上剩下的一个盘子移到C针上；
//3  将n - 1个盘子从B针移到C针上（借助A针）。

#include <iostream>;
using namespace std;
int i{ 0 };
void Move(char src, char dest)
{
	cout << src << "--->" << dest << endl;
	i++;
}

//将n个盘子从src针移动到dest针，以medium针作为中转
void Hanoi(int n,char src,char medium,char dest)
{
	if (n==1)
	{
		Move(src, dest);
	}
	else
	{
		Hanoi(n - 1, src, dest, medium);
		Move(src, dest);
		Hanoi(n - 1, medium, src, dest);
	}
}

int main()
{
	int m;
	cout << "Enter the number of diskes:";
	cin >> m;
	cout << endl;
	cout << "the step to moving " << m << " diskes" << endl;
	Hanoi(m, 'A', 'B', 'C');
	cout << "Account of steps is:" << i << endl;
	return  0;

}


